package pro.softzhang.algo.lc0;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.flag.knowledge.KDoublePointer;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TODO 加练
 */
public class LC15_ThreeSum {
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        // System.out.println(JSON.toJSONString(new Solution().threeSum(nums)));
        System.out.println(JSON.toJSONString(new Solution1().threeSum(nums)));
    }


    /**
     *
     */
    @KDoublePointer
    static
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> triples = new ArrayList<>();

            // 小于3，够不成三元组，免谈
            if(nums.length < 3) {
                return triples;
            }

            // 对数组进行排序，基于排序双指针查找
            Arrays.sort(nums);

            int firstIdx = 0;
            // 先锚定第1个
            while (firstIdx < nums.length - 2) {
                // 具体查找过程
                int secondIdx = firstIdx + 1, thirdIdx = nums.length - 1;
                while (secondIdx < thirdIdx) {
                    int total = nums[firstIdx] + nums[secondIdx] + nums[thirdIdx];
                    if(total == 0) {
                        triples.add(Arrays.asList(nums[firstIdx], nums[secondIdx], nums[thirdIdx]));
                        int secondValue = nums[secondIdx];
                        while (secondIdx < thirdIdx && secondValue == nums[secondIdx]) {
                            secondIdx++;
                        }
                    } else if (total > 0){
                        thirdIdx--;
                    } else {
                        secondIdx++;
                    }
                }

                // 外部排重
                int firstValue = nums[firstIdx];
                while (firstIdx < nums.length - 2 && firstValue == nums[firstIdx]) {
                    firstIdx++;
                }
            }

            return triples;
        }
    }

    /**
     * 时间复杂度O(n^2)
     * 空间复杂度O(1)
     */
    @KDoublePointer
    @XOptimal
    static
    class Solution1 {
        public List<List<Integer>> threeSum(int[] nums) {
            // 排序
            Arrays.sort(nums);

            List<List<Integer>> triples = new ArrayList<>();
            for (int i = 0; i < nums.length - 2; i++) {
                int x = nums[i];
                if (i > 0 && x == nums[i - 1]) {
                    continue;
                }

                // 优化点1，减少计算量
                if (x + nums[i + 1] + nums[i + 2] > 0 ) {
                    break;
                }

                // 优化点2
                if (x + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
                    continue;
                }

                int j = i + 1, k = nums.length - 1;
                while (j < k) {
                    int s = x + nums[j] + nums[k];
                    if (s > 0) {
                        k--;
                    } else if (s < 0) {
                        j++;
                    } else {
                        triples.add(Arrays.asList(x, nums[j], nums[k]));

                        do {
                            j++;
                        } while (j < k && nums[j] == nums[j - 1]);

                        do {
                            k--;
                        } while (k > j && nums[k] == nums[k + 1]);
                    }
                }
            }
            return triples;
        }
    }
}
